package com.leecode.base;

/**
 * @Author: yaoshubin
 * @Date: 2022-12-09 22:22
 * @description :  交换类排序——冒泡排序
 * 稳定性：稳定
 * 时间复杂度：O(n的平方）
 * 空间复杂度：O(1)
 * 对数据敏感，如果一趟没有发生数据交换，则说明元素已经有序
 *
 * <p>
 * 特点：最后一个一定是最大的, 两两换
 */
public class Index_18_冒泡排序 {

    public static void main(String[] args) {

        int nums[] = {1, 6, 4, 2, 9, 5, 5, 6, 8};

        ArrayUtil.printArray(nums);
        ArrayUtil.printArray(bubbleSort(nums));
    }

    public static int[] bubbleSort(int[] nums) {
        int N = nums.length;
        if (nums == null || N == 1) {
            return nums;
        }

        //{1, 6, 4, 2, 9, 5, 5, 6, 8}
        //[0 1 2 3 ... i ... N-1]
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    ArrayUtil.swap(nums, j, j + 1);
                }
            }
        }
        return nums;
    }

}
